package com.adee.zingfront;

/**
 * 现在有一个围棋棋盘（19*19），每个点上都记录有一个随机数值（在 1 到 100 之间），我们在棋盘上面随机画一条直
 * 线（只能横着画或者竖着画，且不经过任何一个点），将棋盘分成 2 部分 A 和 B，A 和 B 棋盘上面数值总和分别为 SumA
 * 和 SumB，现在我们想找出这样一条直线画法，使得 SumA 和 SumB 之间的差值最小，给出此差值即可；注意：不得使用
 * 穷举法；
 *
 * 思路：f = |SumA - SumB|最小值，已知Sum = SumA + SumB，Sum表示全部点的总和，则f = |Sum - 2*SumA|取最小值，
 * 找出和小于等于Sum/2最大值对应的子串即可。
 */
public class Test3 {
    public static void main(String[] args) {
        int[][] arr = new int[19][19];
        arr[1][5] = 9;
        arr[3][2] = 2;
        arr[8][11] = 60;
        arr[10][3] = 13;
        arr[15][1] = 8;
        // 填充值...
        int sum = 0;
        for (int[] row : arr) {
            for (int i : row) {
                sum += i;
            }
        }
        // 行
        int[] rowArr = new int[19];
        for(int i = 0; i < 19; i++) {
            int tempSum = 0;
            for(int j = 0; j < 19; j++) {
                tempSum += arr[i][j];
            }
            rowArr[i] = tempSum;
        }
        int retRow = getMinDiff(rowArr, sum);

        // 列
        int[] colArr = new int[19];
        for(int j = 0; j < 19; j++) {
            int tempSum = 0;
            for(int i = 0; i < 19; i++) {
                tempSum += arr[i][j];
            }
            colArr[j] = tempSum;
        }
        int retCol = getMinDiff(colArr, sum);

        // 比较行列
        System.out.println(Math.min(retRow, retCol));

    }

    // 找出从arr[0]开始的，和最接近sum/2的子串arr[0~i]，返回{最小差值,位置i}
    public static int getMinDiff(int[] arr, int sum) {
        int half = sum/2;
        int max = -1; // 小于等于half的最大值
        int tempSum = 0; // arr[0~i]的和
        for(int i = 0; i < arr.length; i++) {
            tempSum += arr[i];
            if(max == -1) {
                max = tempSum;
            } else {
                if(tempSum <= half) {
                    if (tempSum > max) {
                        max = tempSum;
                    }
                }
            }
        }
        return sum-max-max;
    }
}
